package com.duoduo.树;

import com.duoduo.TreeNode;

import java.util.*;

/**
 * @program: algorithm
 * @description: 二叉树的中序遍历94
 * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
 * 输入：root = [1,null,2,3]
 * 输出：[1,3,2]
 * @author: chaidl  ！
 * @create: 2022-04-11 14:44
 *
 * 中序遍历就是访问左子树以后访问根节点，然后访问右子树
 */
public class 二叉树的中序遍历94 {
	//迭代的方式
	public List<Integer> inorderTraversa2(TreeNode root) {
		List<Integer> result=new ArrayList<Integer>();
		//第一轮循环
		Deque<TreeNode> queue=new LinkedList<TreeNode>();
		//如果root不为空，或者栈不为空，他们两个必须满足一个
		while (root!=null  || !queue.isEmpty()){
			while (root != null){
				//从根节点，因为只能读取，不能输出，值压栈
				queue.push(root);
				//一直找到最左边的第一个叶子结点才会停止循环
				root=root.left;
			}
			root=queue.pop();
			result.add(root.val);
			root = root.right;
		}
		return result;
	}
	// 采用递归解法
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> result=new ArrayList<Integer>();
		accessTree(root,result);
		return result;
	}
	// 采用递归解法
	private void accessTree(TreeNode root, List<Integer> result) {
		if (root == null){
			return;
		}
		//访问根节点的左子树
		accessTree(root.left,result);
		//将根节点本身加入集合
		result.add(root.val);
		//访问根节点的右子树
		accessTree(root.right,result);
	}
}
